package com.lisp.algorithm.test.sort;

import java.util.Arrays;
import java.util.Random;

public class QuickSortHoare {

	public static void main(String[] args) {
		int data[] = {1, 2};
		quickSort(data, 0, data.length-1);
		System.out.println(Arrays.toString(data));
	}
	
	private static void quickSort(int data[], int start, int end) {
		if(start < end) {
			int partitionIndex = partition(data, start, end);
			quickSort(data, start, partitionIndex);
			quickSort(data, partitionIndex+1, end);
		}
	}
	
	// start inclusive, end inclusive
	private static int partition(int data[], int start, int end) {
		Random r = new Random();
		int choseIndex = start + r.nextInt(end-start);
		int pivot = data[choseIndex];
		int lessEqualIndex = start-1;
		int greaterEqualIndex = end+1;
		while(true) {
			do{
				lessEqualIndex++;
			}while(data[lessEqualIndex] < pivot);
			
			do{
				greaterEqualIndex--;
			}while(data[greaterEqualIndex] > pivot);
			
			if(lessEqualIndex < greaterEqualIndex) {
				ArrayUtils.swap(data, lessEqualIndex, greaterEqualIndex);
			} else {
				return greaterEqualIndex;
			}
		}
	}
}
